package org.labuladong.经典贪心算法;

import org.jikeshijian.Solution;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-22:49
 * @Description:
 *
 * 标签：动态规划，贪⼼算法，⼀维动态规划
 * 给你⼀个⾮负整数数组 nums，你最初位于数组的第⼀个位置，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，请你使⽤最少的跳跃次数到达数组的最后⼀个位置（假设你总是可以到达数组的最后⼀个位置）。
 * 示例 1:
 * 输⼊：nums = [2,3,1,1,4]
 * 输出：2
 * 解释：跳到最后⼀个位置的最⼩跳跃数是 2。
 *  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后⼀个位置。
 * @version: 1.0
 */
public class LC_45跳跃游戏II2 {
		public int jump(int[] nums) {
			int n = nums.length;
			if (n <= 1) return 0;

			int end = 0; // 当前可以到达的最远位置
			int far = 0; // 在当前位置的基础上可以到达的最远位置
			int minJump = 0; // 最小跳跃次数

			for (int i = 0; i < n - 1; i++) {
				far = Math.max(far, i + nums[i]); // 更新最远位置
				if (i == end) { // 如果到达了之前计算的最远位置
					minJump++; // 增加跳跃次数
					end = far; // 更新最远位置
				}
			}

			return minJump;
		}

		public static void main(String[] args) {
			LC_45跳跃游戏II2 solution = new LC_45跳跃游戏II2();
			int[] nums = {2, 3, 1, 1, 4};
			System.out.println(solution.jump(nums)); // 输出应该是 2
		}
	}